{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Paths with Sum LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求和路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。</p>\n",
    "\n",
    "<p><strong>示例:</strong><br>\n",
    "给定如下二叉树，以及目标和&nbsp;<code>sum = 22</code>，</p>\n",
    "\n",
    "<pre>              5\n",
    "             / \\\n",
    "            4   8\n",
    "           /   / \\\n",
    "          11  13  4\n",
    "         /  \\    / \\\n",
    "        7    2  5   1\n",
    "</pre>\n",
    "\n",
    "<p>返回:</p>\n",
    "\n",
    "<pre>3\n",
    "<strong>解释：</strong>和为 22&nbsp;的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]</pre>\n",
    "\n",
    "<p>提示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>节点总数 &lt;= 10000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [paths-with-sum-lcci](https://leetcode.cn/problems/paths-with-sum-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [paths-with-sum-lcci](https://leetcode.cn/problems/paths-with-sum-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.nodes = {}\n",
    "        for num in nums:\n",
    "            code = num // 10\n",
    "            val = num % 10\n",
    "            self.nodes[code] = val\n",
    "\n",
    "        root = nums[0] // 10\n",
    "\n",
    "        self.res = 0\n",
    "        self.traverse(root, 0)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if root not in self.nodes:\n",
    "            return \n",
    "\n",
    "        path += self.nodes[root]\n",
    "\n",
    "        row, col = self.decode(root)\n",
    "        left = (row + 1) * 10 + (2 * col - 1)\n",
    "        right = (row + 1) * 10 + (2 * col)\n",
    "\n",
    "        if left not in self.nodes and right not in self.nodes:\n",
    "            self.res += path\n",
    "\n",
    "        self.traverse(left, path)\n",
    "        self.traverse(right, path)\n",
    "\n",
    "    def decode(self, code):\n",
    "        row = code // 10\n",
    "        col = code % 10\n",
    "        return row, col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = [[None] * (2**i) for i in range(4)]\n",
    "        total = 0\n",
    "\n",
    "        for num in nums:\n",
    "            d = (num//100) - 1\n",
    "            p = ((num//10) % 10) - 1\n",
    "            v = num % 10\n",
    "\n",
    "            tree[d][p] = [v, True]\n",
    "        \n",
    "        for d in range(3, -1, -1):\n",
    "            for p, node in enumerate(tree[d]):\n",
    "                if not node or not node[1]:\n",
    "                    continue\n",
    "                \n",
    "                s = 0\n",
    "                d_ = d\n",
    "                p_ = p\n",
    "                while d_ >= 0:\n",
    "                    s += tree[d_][p_][0]\n",
    "                    tree[d_][p_][1] = False\n",
    "                    d_ -= 1\n",
    "                    p_ //= 2\n",
    "                \n",
    "                total += s\n",
    "        \n",
    "        return total\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for num in nums:\n",
    "            d, p, v = num // 100, num // 10 % 10, num % 10\n",
    "            fa = (d - 1, (p + 1) // 2)\n",
    "            cnt[(d, p)] += cnt[fa] + v\n",
    "        res = 0\n",
    "        for (d, p), v in cnt.items():\n",
    "            if (d + 1, p * 2 - 1) not in cnt and (d + 1, p * 2) not in cnt:\n",
    "                res += v\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        # print(1//2) # 0\n",
    "        rootToPath = dict() # 从key到root的path sum, root为1\n",
    "        rootToPath[0] = 0\n",
    "        for num in nums:\n",
    "            depth = num // 100\n",
    "            pos = num // 10 % 10\n",
    "            val = num % 10\n",
    "            idx = 2**(depth - 1) + pos - 1\n",
    "            rootToPath[idx] = rootToPath[idx//2] + val\n",
    "        res = 0\n",
    "        for path, val in rootToPath.items():\n",
    "            if not path * 2 in rootToPath and not path * 2 + 1 in rootToPath:\n",
    "            # if leaf node\n",
    "                res += val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        H = nums[-1] // 100\n",
    "        lst = [0] * (2**H)\n",
    "        i = len(nums) - 1\n",
    "        res = 0\n",
    "        for l in range(H, 0, -1):\n",
    "            new_lst = []\n",
    "            for j in range(2 ** (l - 1)):\n",
    "                new_lst.append(lst[2 * j] + lst[2 * j + 1])\n",
    "\n",
    "            while i >= 0 and nums[i] // 100 >= l:\n",
    "                v = nums[i] % 10\n",
    "                p = (nums[i] // 10) % 10\n",
    "                if new_lst[p-1] == 0:\n",
    "                    new_lst[p-1] = 1\n",
    "                res += v * new_lst[p-1]\n",
    "                i -= 1\n",
    "\n",
    "            lst = new_lst\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = defaultdict(list)\n",
    "\n",
    "        for node in nums:\n",
    "            level = node // 100\n",
    "            position = (node - (level * 100)) // 10\n",
    "            value = node % 10\n",
    "            tree[level*10 + position].append(value)\n",
    "            parent_level = level - 1\n",
    "            parent_position = (position + 1) // 2\n",
    "            if (parent_level * 10 + parent_position) in tree:\n",
    "                tree[(parent_level * 10 + parent_position) ].append(level*10 + position)\n",
    "\n",
    "        print(tree)\n",
    "        path = []\n",
    "        self.dfs(11, tree, 0, path)\n",
    "        add_up = 0 \n",
    "        for i in path:\n",
    "            add_up += i\n",
    "        return add_up\n",
    "\n",
    "    def dfs(self, node, tree, cur_sum, path):\n",
    "        if len(tree[node]) < 2: # leave node\n",
    "            cur_sum += tree[node][0]\n",
    "            path.append(cur_sum)\n",
    "            return \n",
    "\n",
    "        cur_sum += tree[node][0] # add current node value to the sum value\n",
    "        self.dfs(tree[node][1], tree, cur_sum, path)\n",
    "        if len(tree[node]) > 2:\n",
    "            self.dfs(tree[node][2], tree, cur_sum, path)\n",
    "        return\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        dic = defaultdict(int) # key (row, col) -> val\n",
    "        for num in nums:\n",
    "            h = num // 100\n",
    "            d = (num//10) % 10\n",
    "            dic[(h, d)] += dic[(h-1, (d+1)//2)] + num % 10  # 113 % 10 = 3\n",
    "        res = 0\n",
    "        for (h, d), v in dic.items():\n",
    "            if (h+1, 2*d-1) not in dic and (h+1, 2*d) not in dic:\n",
    "                res += v\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#       11\n",
    "#    21    22\n",
    "#   31 32 33 34\n",
    "\n",
    "#    d \n",
    "#    2*(d-1) + 1 = 2d-1\n",
    "#    2*(d-1) + 2 = 2d\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        cnt=Counter()\n",
    "        for num in nums:\n",
    "            d,p,v=num//100,(num//10)%10,num%10\n",
    "            fa=(d-1,(p+1)//2)\n",
    "            cnt[(d,p)]+=cnt[fa]+v\n",
    "\n",
    "        res=0\n",
    "        for (d,p),v in cnt.items():\n",
    "            if (d+1,p*2-1) not in cnt and (d+1,p*2) not in cnt:\n",
    "                res+=v\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        l = [-1] * 31\n",
    "        for n in nums:\n",
    "            d = n // 100\n",
    "            p = (n // 10) % 10\n",
    "            v = n % 10\n",
    "            i = 2 ** (d - 1) - 1 + p - 1\n",
    "            l[i] = v\n",
    "\n",
    "        self.ret = 0\n",
    "        def dfs(i, s, l):\n",
    "            s += l[i]\n",
    "            lc = 2 * i + 1\n",
    "            rc = 2 * i + 2\n",
    "            bl = l[lc] > -1\n",
    "            br = l[rc] > -1\n",
    "            if not bl and not br:\n",
    "                self.ret += s\n",
    "                return\n",
    "            if bl:\n",
    "                dfs(lc, s, l)\n",
    "            if br:\n",
    "                dfs(rc, s, l)\n",
    "        dfs(0, 0, l)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        value = {(1,1): int(nums[0]%10)}\n",
    "        for num in nums:\n",
    "            if int(num / 100) > 1:\n",
    "                str_num = str(num)\n",
    "                f, s, v = int(str_num[0]), int(str_num[1]), int(str_num[2])\n",
    "                father = (f-1, int((s+1)/2))\n",
    "                value[(f,s)] = value[father] + v\n",
    "        res = 0\n",
    "        for (f,s) ,v in value.items():\n",
    "            if (f+1 , s*2-1) not in value and (f+1, s*2) not in value:\n",
    "                res += v\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = defaultdict(list)\n",
    "\n",
    "        for node in nums:\n",
    "            level = node // 100\n",
    "            position = (node - (level * 100)) // 10\n",
    "            value = node % 10\n",
    "            tree[level*10 + position].append(value)\n",
    "            parent_level = level - 1\n",
    "            parent_position = (position + 1) // 2\n",
    "            if (parent_level * 10 + parent_position) in tree:\n",
    "                tree[(parent_level * 10 + parent_position) ].append(level*10 + position)\n",
    "        path = []\n",
    "        self.dfs(11, tree, 0, path)\n",
    "        add_up = 0 \n",
    "        for i in path:\n",
    "            add_up += i\n",
    "        return add_up\n",
    "\n",
    "    def dfs(self, node, tree, cur_sum, path):\n",
    "        if len(tree[node]) < 2: # leave node\n",
    "            cur_sum += tree[node][0]\n",
    "            path.append(cur_sum)\n",
    "            return \n",
    "\n",
    "        cur_sum += tree[node][0] # add current node value to the sum value\n",
    "        self.dfs(tree[node][1], tree, cur_sum, path)\n",
    "        if len(tree[node]) > 2:\n",
    "            self.dfs(tree[node][2], tree, cur_sum, path)\n",
    "        return\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(lambda: defaultdict(int))\n",
    "\n",
    "        for num in nums:\n",
    "            dep = num // 100\n",
    "            pos = (num//10) % 10\n",
    "            val = num % 10\n",
    "            d[dep][pos] = val\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        def dfs(dep, pos, cur):\n",
    "            if dep not in d or pos not in d[dep]:\n",
    "                return 0\n",
    "\n",
    "            cur += d[dep][pos]\n",
    "\n",
    "            left = dfs(dep+1, 2*pos-1, cur)\n",
    "\n",
    "            right = dfs(dep+1, 2*pos, cur)\n",
    "\n",
    "            if left == 0 and right == 0:\n",
    "                nonlocal ret\n",
    "                ret += cur\n",
    "                return\n",
    "\n",
    "        dfs(1, 1, 0)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        # print(1//2) # 0\n",
    "        rootToPath = dict() # 从key到root的path sum, root为1\n",
    "        rootToPath[0] = 0\n",
    "        for num in nums:\n",
    "            depth = num // 100\n",
    "            pos = num // 10 % 10\n",
    "            val = num % 10\n",
    "            idx = 2**(depth - 1) + pos - 1\n",
    "            rootToPath[idx] = rootToPath[idx//2] + val\n",
    "        res = 0\n",
    "        for path, val in rootToPath.items():\n",
    "            if not path * 2 in rootToPath and not path * 2 + 1 in rootToPath:\n",
    "            # if leaf node\n",
    "                res += val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 记录从根节点到当前节点的路径和【设：根节点索引从1开始】\n",
    "        dic = dict()\n",
    "        dic[0] = 0 # 初始化\n",
    "\n",
    "        # 自己画个图，就知道当前节点k的左节点索引为2*k，右节点索引为2*k+1\n",
    "        # 所以当前索引为k的话，那其父母索引为k//2\n",
    "        for n in nums:\n",
    "            # idx = 2*(depth-1) + (pos-1)\n",
    "            idx = 2**(n//100-1) + ((n//10)%10-1)\n",
    "            dic[idx] = dic[idx//2] + n%10\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for k in dic:\n",
    "            left_idx = 2*k\n",
    "            right_idx = 2*k+1\n",
    "\n",
    "            # 如果为叶子节点\n",
    "            if left_idx not in dic and right_idx not in dic:\n",
    "\n",
    "                res += dic[k]\n",
    "        \n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(lambda: defaultdict(int))\n",
    "\n",
    "        for num in nums:\n",
    "            dep = num // 100\n",
    "            pos = (num//10) % 10\n",
    "            val = num % 10\n",
    "            d[dep][pos] = val\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        def dfs(dep, pos, cur):\n",
    "            if dep not in d or pos not in d[dep]:\n",
    "                return -1\n",
    "\n",
    "            cur += d[dep][pos]\n",
    "\n",
    "            left = dfs(dep+1, 2*pos-1, cur)\n",
    "\n",
    "            right = dfs(dep+1, 2*pos, cur)\n",
    "\n",
    "            if left == -1 and right == -1:\n",
    "                nonlocal ret\n",
    "                ret += cur\n",
    "                # print\n",
    "                return\n",
    "\n",
    "        dfs(1, 1, 0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 记录从根节点到当前节点的路径和【设：根节点索引从1开始】\n",
    "        dic = dict()\n",
    "        dic[0] = 0 # 初始化\n",
    "\n",
    "        # 自己画个图，就知道当前节点k的左节点索引为2*k，右节点索引为2*k+1\n",
    "        # 所以当前索引为k的话，那其父母索引为k//2\n",
    "        for n in nums:\n",
    "            idx = 2**(n//100-1) + ((n//10)%10-1)\n",
    "            dic[idx] = dic[idx//2] + n%10\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for k in dic:\n",
    "            left_idx = 2*k\n",
    "            right_idx = 2*k+1\n",
    "\n",
    "            # 如果为叶子节点\n",
    "            if left_idx not in dic and right_idx not in dic:\n",
    "\n",
    "                res += dic[k]\n",
    "        \n",
    "        return res\n",
    "            \n",
    "#  2^n-1\n",
    "# [1]\n",
    "\n",
    "#    i\n",
    "#  0 1 2  father-> (i-1)//2\n",
    "# [1,2,3]  \n",
    "# left: 2*i+1\n",
    "# right:2*i+2\n",
    "\n",
    "# idx = 1\n",
    "# 2,1\n",
    "# [1] - 2**n-1\n",
    "\n",
    "\n",
    "\n",
    "#                 113      1 - 1                              1\n",
    "#                 /  \\                                        /\\\n",
    "#             215     221  2 - 2**2-1 = 3       2-1+1-1 = 2      2-1+2-1 = 3    \n",
    "#             /\\       /\\\n",
    "#                          3 - 1+2+4=7 = 2**3-1\n",
    "\n",
    "# [0(3), 1(5), 2(1)]\n",
    "\n",
    "# h = num//100           idx = 2**(h-1) - 1 + d    2-1+2-1 = 2\n",
    "# d = (num//10)%10\n",
    "# o = num%10\n",
    "\n",
    "# i: father -> (i-1)//2\n",
    "# left: 2*i+1\n",
    "# right:2*i+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        l = [-1] * 15\n",
    "        for n in nums:\n",
    "            d = n // 100\n",
    "            p = (n // 10) % 10\n",
    "            v = n % 10\n",
    "            i = 2 ** (d - 1) - 1 + p - 1\n",
    "            #print(f'{n} {d} {p} {v} {i}')\n",
    "            l[i] = v\n",
    "\n",
    "        self.ret = 0\n",
    "        def dfs(i, s, l):\n",
    "            s += l[i]\n",
    "            lc = 2 * i + 1\n",
    "            rc = 2 * i + 2\n",
    "            bl = lc < 15 and l[lc] > -1\n",
    "            br = rc < 15 and l[rc] > -1\n",
    "            if not bl and not br:\n",
    "                self.ret += s\n",
    "                return\n",
    "            if bl:\n",
    "                dfs(lc, s, l)\n",
    "            if br:\n",
    "                dfs(rc, s, l)\n",
    "        dfs(0, 0, l)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,v):\n",
    "        self.v=v\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        hashmap={}\n",
    "        for num in nums[1:]:\n",
    "            x,y,z=num//100,num//10%10,num%10\n",
    "            seq=pow(2,x-1)+y-1\n",
    "            hashmap[seq]=Node(z)\n",
    "        hashmap[1]=Node(nums[0]%10)\n",
    "        ans=0\n",
    "        def dfs(seq,sum):\n",
    "            nonlocal ans\n",
    "            if seq*2 not in hashmap and seq*2+1 not in hashmap:\n",
    "                sum+=hashmap[seq].v\n",
    "                ans+=sum\n",
    "                return\n",
    "            if seq*2 in hashmap:\n",
    "                dfs(seq*2,sum+hashmap[seq].v)\n",
    "            if seq*2+1 in hashmap:\n",
    "                dfs(seq*2+1,sum+hashmap[seq].v)\n",
    "        dfs(1,0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        root = Node(nums[0] % 10)\n",
    "        for x in nums[1:]:\n",
    "            depth, pos, val = x // 100, x // 10 % 10, x % 10\n",
    "            pos -= 1\n",
    "            curr = root\n",
    "            for d in range(depth - 2, -1, -1):\n",
    "                if pos < 2 ** d:\n",
    "                    curr.left = curr = curr.left or Node(val)\n",
    "                else:\n",
    "                    curr.right = curr = curr.right or Node(val)\n",
    "                pos %= 2 ** d\n",
    "        \n",
    "        def dfs(node, running_sum):\n",
    "            if not node:\n",
    "                return\n",
    "            running_sum += node.val\n",
    "            if not node.left and not node.right:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(node.left, running_sum)\n",
    "                dfs(node.right, running_sum)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        que = Counter()\n",
    "        for i in nums:\n",
    "            layer, idx, val = map(int, str(i))\n",
    "            que[2 ** (layer - 1) + idx - 1] = val \n",
    "        \n",
    "        def dfs(node, x):\n",
    "            nonlocal ans \n",
    "            if 2 * node in que:\n",
    "                dfs(2 * node, x + que[2 * node])\n",
    "            if 2 * node + 1 in que:\n",
    "                dfs(2 * node + 1, x + que[2 * node + 1])\n",
    "            if 2 * node not in que and 2 * node + 1 not in que:\n",
    "                ans += x \n",
    "        \n",
    "        dfs(1, que[1])\n",
    "        return ans \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.node_map = {}\n",
    "\n",
    "        for num in nums:\n",
    "            val = num % 10\n",
    "            code = num // 10\n",
    "\n",
    "            self.node_map[code] = val \n",
    "\n",
    "        root = nums[0] // 10\n",
    "\n",
    "        self.res = 0\n",
    "\n",
    "        self.traverse(root, 0)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if root not in self.node_map:\n",
    "            return \n",
    "\n",
    "        path += self.node_map[root]\n",
    "\n",
    "        root_row, root_col = self.decode(root)\n",
    "        left = (root_row + 1) * 10 + (2 * root_col - 1)\n",
    "        right = (root_row + 1) * 10 + (2 * root_col)\n",
    "\n",
    "        if left not in self.node_map and right not in self.node_map:\n",
    "            self.res += path \n",
    "            return \n",
    "\n",
    "        self.traverse(left, path)\n",
    "        self.traverse(right, path)\n",
    "\n",
    "    def decode(self, code):\n",
    "        row = code // 10\n",
    "        col = code % 10\n",
    "        return row, col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        values = {x // 10: x % 10 for x in nums}\n",
    "\n",
    "        def dfs(node, total): # node是每个num的前两位数\n",
    "            if node not in values: return\n",
    "            total += values[node]\n",
    "            depth, pos = node // 10, node % 10\n",
    "            left = (depth + 1) * 10 + 2 * pos - 1\n",
    "            right = left + 1\n",
    "\n",
    "            # 如果node是叶子节点，更新self.res\n",
    "            if left not in values and right not in values:\n",
    "                self.res += total\n",
    "            else:\n",
    "                dfs(left, total)\n",
    "                dfs(right, total)\n",
    "\n",
    "        dfs(nums[0]//10, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        m = defaultdict(lambda: defaultdict(int))\n",
    "        mx = 0\n",
    "        for i, c in enumerate(nums):\n",
    "            depth = c // 100\n",
    "            mx = max(mx, depth)\n",
    "            c %= 100\n",
    "            pos = c // 10\n",
    "            val = c % 10\n",
    "            m[depth][pos] = val\n",
    "        ans = 0\n",
    "        # 叶子节点 不一定是深度最深的节点\n",
    "        depth_set = list(m.keys())\n",
    "        for depth in depth_set:\n",
    "            for pos in m[depth]:\n",
    "                if (2 * pos - 1) not in m[depth+1] and (2 * pos) not in m[depth+1]:\n",
    "                    cur = 0\n",
    "                    cur_layer = depth\n",
    "                    while cur_layer:\n",
    "                        cur += m[cur_layer][pos]\n",
    "                        pos = (pos + 1) >> 1\n",
    "                        cur_layer -= 1\n",
    "                    ans += cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.nodes = {}\n",
    "\n",
    "        for ele in nums:\n",
    "            code = ele // 10\n",
    "            val = ele % 10\n",
    "            self.nodes[code] = val\n",
    "\n",
    "        root = nums[0] // 10\n",
    "\n",
    "        self.res = 0\n",
    "        self.traverse(root, 0)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path_sum):\n",
    "        if root not in self.nodes:\n",
    "            return \n",
    "\n",
    "        row, col = self.decode(root)\n",
    "\n",
    "        left = (row + 1) * 10 + (col * 2 - 1)\n",
    "        right = (row + 1) * 10 + (col * 2)\n",
    "\n",
    "        path_sum += self.nodes[root]\n",
    "\n",
    "        if left not in self.nodes and right not in self.nodes:\n",
    "            self.res += path_sum\n",
    "            return\n",
    "\n",
    "        self.traverse(left, path_sum)\n",
    "        self.traverse(right, path_sum)\n",
    "\n",
    "    def decode(self, code):\n",
    "        row = code // 10\n",
    "        col = code % 10\n",
    "\n",
    "        return row, col\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = {(n // 100, n // 10 % 10): n % 10 for n in nums}\n",
    "\n",
    "        def dfs(node, currSum):\n",
    "\n",
    "            if not node in tree:\n",
    "                return 0\n",
    "            \n",
    "            currSum += tree[node]\n",
    "\n",
    "            layer, pos = node\n",
    "            left = (layer + 1, pos * 2 - 1)\n",
    "            right = (layer + 1, pos * 2)\n",
    "\n",
    "            if not left in tree and not right in tree:\n",
    "                return currSum\n",
    "            \n",
    "            return dfs(left, currSum) + dfs(right, currSum)\n",
    "        \n",
    "        return dfs((1, 1), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        layers = []\n",
    "        \n",
    "        for i in range(1,5):\n",
    "            layers.append([-1 for _ in range(2**(i-1))])\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            cur = nums[i]\n",
    "            x = cur // 100\n",
    "            y = (cur // 10) % 10\n",
    "            v = cur % 10\n",
    "            layers[x-1][y-1] = v\n",
    "        \n",
    "        root = TreeNode(layers[0][0])\n",
    "        layers[0][0] = root\n",
    "\n",
    "        for i in range(len(layers)-1):\n",
    "            for j in range(len(layers[i])):\n",
    "                cur = layers[i][j]\n",
    "                if cur == -1:\n",
    "                    continue\n",
    "                \n",
    "                if layers[i+1][j*2] != -1:\n",
    "                    l = TreeNode(layers[i+1][j*2])\n",
    "                    cur.left = l\n",
    "                    layers[i+1][j*2] = l\n",
    "                \n",
    "                if layers[i+1][j*2+1] != -1:\n",
    "                    r = TreeNode(layers[i+1][j*2+1])\n",
    "                    cur.right = r\n",
    "                    layers[i+1][j*2+1] = r\n",
    "        for x in layers:\n",
    "            print(x)\n",
    "\n",
    "        def dfs(node, cur):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            if not node.left and not node.right:\n",
    "                return node.val + cur\n",
    "            \n",
    "            l = dfs(node.left, cur + node.val)\n",
    "            r = dfs(node.right, cur + node.val)\n",
    "\n",
    "            return l + r\n",
    "\n",
    "        return dfs(root, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tol = 1<<5\n",
    "        l = [-1]*tol\n",
    "        for num in nums:\n",
    "            d = num // 100\n",
    "            p = (num%100)//10\n",
    "            v = num%10\n",
    "            id = (1<<(d-1)) - 1 + (p-1)\n",
    "            l[id]=v\n",
    "        ans = 0\n",
    "        # print(l)\n",
    "        for i in range(16):\n",
    "            if l[i]==-1:\n",
    "                continue\n",
    "            if l[2*i+1]==-1 and l[2*i+2]==-1:\n",
    "                ans+=l[i]\n",
    "            else:\n",
    "                if l[2*i+2]!=-1:\n",
    "                    l[2*i+2]+=l[i]\n",
    "                if l[2*i+1]!=-1:\n",
    "                    l[2*i+1]+=l[i]\n",
    "            # print(l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        def dfs(d, p, curr_sum):\n",
    "            if (d, p) not in nodes:\n",
    "                return  0\n",
    "\n",
    "            curr_sum += nodes[(d, p)]\n",
    "            if (d + 1, 2 * p - 1) not in nodes and (d + 1, 2 * p) not in nodes:\n",
    "                return curr_sum\n",
    "            return dfs(d + 1, 2 * p - 1, curr_sum) + dfs(d + 1, 2 * p, curr_sum)\n",
    "        \n",
    "        nodes = {}\n",
    "        for num in nums:\n",
    "            d, p, v = num // 100, num // 10 % 10, num % 10\n",
    "            nodes[(d, p)] = v\n",
    "        \n",
    "        return dfs(1, 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        values = {x // 10: x % 10 for x in nums}\n",
    "        def dfs(node, running_sum = 0):\n",
    "            if node not in values: return\n",
    "            running_sum += values[node]\n",
    "            depth, pos = divmod(node, 10)\n",
    "            left = (depth + 1) * 10 + 2 * pos - 1\n",
    "            right = left + 1\n",
    "\n",
    "            if left not in values and right not in values:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(left, running_sum)\n",
    "                dfs(right, running_sum)\n",
    "\n",
    "        dfs(nums[0] // 10)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        dic[0] = 0\n",
    "        for num in nums:\n",
    "            h = num // 100          #\n",
    "            d = (num // 10) % 10    #\n",
    "            idx = 2**(h-1) + d - 1  #  11 -> 1, 21 -> 2\n",
    "            dic[idx] = dic[idx//2] + num%10\n",
    "        res = 0\n",
    "        for i in dic.keys():\n",
    "            left = 2*(i-1) + 1 + 1\n",
    "            right = 2*(i-1) + 2 + 1\n",
    "            if left not in dic and right not in dic:\n",
    "                res += dic[i]\n",
    "        return res\n",
    "\n",
    "\n",
    "#  2^n-1\n",
    "# [1]\n",
    "\n",
    "#    i\n",
    "#  0 1 2  father-> (i-1)//2\n",
    "# [1,2,3]  \n",
    "# left: 2*i+1\n",
    "# right:2*i+2\n",
    "\n",
    "# idx = 1\n",
    "# 2,1\n",
    "# [1] - 2**n-1\n",
    "\n",
    "\n",
    "\n",
    "#                 113      1 - 1                              1\n",
    "#                 /  \\                                        /\\\n",
    "#             215     221  2 - 2**2-1 = 3       2-1+1-1 = 2      2-1+2-1 = 3    \n",
    "#             /\\       /\\\n",
    "#                          3 - 1+2+4=7 = 2**3-1\n",
    "\n",
    "# [0(3), 1(5), 2(1)]\n",
    "\n",
    "# h = num//100           idx = 2**(h-1) - 1 + d    2-1+2-1 = 2\n",
    "# d = (num//10)%10\n",
    "# o = num%10\n",
    "\n",
    "# i: father -> (i-1)//2\n",
    "# left: 2*i+1\n",
    "# right:2*i+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = {}\n",
    "        \n",
    "        for num in nums:\n",
    "            depth = num // 100\n",
    "            pos = num // 10 % 10\n",
    "            val = num % 10\n",
    "\n",
    "            k = 2 ** (depth - 1) + pos - 1\n",
    "            tree[k] = val\n",
    "        # print(tree)\n",
    "        res = 0\n",
    "        def dfs(path, i):\n",
    "            if i not in tree:\n",
    "                return\n",
    "            path += tree[i]\n",
    "            if i * 2 not in tree and i * 2 + 1 not in tree:\n",
    "                nonlocal res\n",
    "                res += path\n",
    "\n",
    "            if i * 2 in tree:\n",
    "                dfs(path, i * 2)\n",
    "\n",
    "            if i * 2 + 1 in tree:\n",
    "                dfs(path, i * 2 + 1)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        dfs(0,1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.pathsum = 0\n",
    "        n = len(nums)\n",
    "        node_dict = {}\n",
    "        maxLayer = 1\n",
    "        for i in range(n):\n",
    "            layer = nums[i] // 100\n",
    "            maxLayer = max(maxLayer, layer)\n",
    "            index = (nums[i] - layer * 100) // 10\n",
    "            value = nums[i] - layer * 100 - index * 10\n",
    "            node_dict[(layer, index)] = [value, i]\n",
    "        \n",
    "        def dfs(begin, path_sum):\n",
    "            if not begin < n:\n",
    "                return\n",
    "            # path_sum = 0\n",
    "            layer = nums[begin] // 100\n",
    "            index =(nums[begin] - layer * 100) // 10\n",
    "            value = node_dict[(layer,index)][0]\n",
    "            path_sum += value\n",
    "            \n",
    "            left_index = index * 2 - 1\n",
    "            right_index = index * 2\n",
    "            if (layer+1, left_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, left_index)][1], path_sum)\n",
    "            if (layer+1, right_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, right_index)][1], path_sum)\n",
    "            if (layer+1, left_index) not in node_dict and (layer+1, right_index) not in node_dict:\n",
    "                self.pathsum += path_sum\n",
    "            \n",
    "        dfs(0, 0)\n",
    "        return self.pathsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = {}\n",
    "        \n",
    "        for v in nums:\n",
    "            depthPos = v // 10\n",
    "            val = v % 10\n",
    "            tree[depthPos] = val\n",
    "        @cache\n",
    "        def dfs(depthPos,curSum):\n",
    "            if depthPos not in tree:\n",
    "                return 0\n",
    "\n",
    "            depth = depthPos // 10 + 1\n",
    "            pos = 2 * (depthPos % 10) - 1\n",
    "\n",
    "            leftDP = depth * 10 + pos\n",
    "            rightDP = leftDP + 1\n",
    "\n",
    "            if leftDP not in tree and rightDP not in tree:\n",
    "                return tree[depthPos] + curSum\n",
    "\n",
    "            l = dfs(leftDP,curSum + tree[depthPos])\n",
    "            r = dfs(rightDP,curSum + tree[depthPos])\n",
    "\n",
    "            return l + r\n",
    "        \n",
    "        return dfs(11,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val: int, left: TreeNode = None, right: TreeNode = None) -> TreeNode:\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        dic = dict()\n",
    "\n",
    "        for num in nums[::-1]:\n",
    "            d = num // 100\n",
    "            p = (num // 10) % 10 - 1\n",
    "            v = num % 10\n",
    "\n",
    "            node = TreeNode(v)\n",
    "            lc = (d+1, p*2)\n",
    "            rc = (d+1, p*2+1)\n",
    "\n",
    "            if lc in dic:\n",
    "                node.left = dic[lc]\n",
    "            if rc in dic:\n",
    "                node.right = dic[rc]\n",
    "            \n",
    "            dic[(d, p)] = node\n",
    "        \n",
    "        res = 0\n",
    "        def pSum(root: TreeNode, preSum: int) -> None:\n",
    "            nonlocal res\n",
    "\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            preSum += root.val\n",
    "            if not root.left and not root.right:\n",
    "                res += preSum\n",
    "                return\n",
    "            \n",
    "            pSum(root.left, preSum)\n",
    "            pSum(root.right, preSum)\n",
    "        \n",
    "        pSum(dic[(1,0)], 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        d = {x // 10 : x % 10 for x in nums}\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x,s):\n",
    "            if x in d:\n",
    "                nonlocal ans\n",
    "                s += d[x]\n",
    "                depth,pos = x // 10,x % 10\n",
    "                left = (depth + 1) * 10 + 2*pos - 1\n",
    "                if left not in d and left + 1 not in d:\n",
    "                    ans += s\n",
    "                else:\n",
    "                    dfs(left,s)\n",
    "                    dfs(left + 1,s)\n",
    "        \n",
    "        dfs(nums[0] // 10,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        nodes = {}\n",
    "        for num in nums:\n",
    "            level = num // 100\n",
    "            num %= 100\n",
    "            col = num // 10\n",
    "            num %= 10\n",
    "            val = num\n",
    "            nodes[(level, col)] = val\n",
    "        \n",
    "        totalSum = 0\n",
    "        def _DFS(level, col, curSum):\n",
    "            nonlocal totalSum\n",
    "            # left child\n",
    "            curSum += nodes[(level, col)]\n",
    "            if (level + 1, col * 2 - 1) in nodes or (level + 1, col * 2) in nodes:\n",
    "                if (level + 1, col * 2 - 1) in nodes:\n",
    "                    _DFS(level + 1, col * 2 - 1, curSum)\n",
    "                if (level + 1, col * 2) in nodes:\n",
    "                    _DFS(level + 1, col * 2, curSum)\n",
    "            else:\n",
    "                totalSum += curSum\n",
    "        \n",
    "        _DFS(1, 1, 0)\n",
    "        \n",
    "        return totalSum\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        # nums: 前序遍历\n",
    "        # convert nums to string of nums\n",
    "        nums_str = [str(x) for x in nums]\n",
    "        prefix_to_num = dict()\n",
    "        for x in nums_str:\n",
    "            prefix_to_num[x[:2]] = x\n",
    "\n",
    "        def code2info(num) -> List[int]:\n",
    "            res = [int(c) for c in num]\n",
    "            return res\n",
    "\n",
    "        all_sum = 0\n",
    "        # queue: (curr_node, curr_path_sum(included curr_node's val))\n",
    "        queue = [(nums_str[0], int(nums_str[0][2]))]\n",
    "        while queue:\n",
    "            curr_node, curr_sum = queue.pop(0)\n",
    "            curr_info = code2info(curr_node)\n",
    "            left_prefix = str(curr_info[0]+1) + str(2*curr_info[1]-1)\n",
    "            right_prefix = str(curr_info[0]+1) + str(2*curr_info[1])\n",
    "\n",
    "            # if curr_node is leaf nonde\n",
    "            if left_prefix not in prefix_to_num and right_prefix not in prefix_to_num:\n",
    "                all_sum += curr_sum\n",
    "                continue\n",
    "            \n",
    "            # if has left child\n",
    "            if left_prefix in prefix_to_num:\n",
    "                left_child = prefix_to_num[left_prefix]\n",
    "                queue.append((left_child, curr_sum + int(left_child[2])))\n",
    "            \n",
    "            # if has right child\n",
    "            if right_prefix in prefix_to_num:\n",
    "                right_child = prefix_to_num[right_prefix]\n",
    "                queue.append((right_child, curr_sum + int(right_child[2])))\n",
    "        \n",
    "        return all_sum\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val: int):\n",
    "        self.val = val\n",
    "        self.left = self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        root = Node(nums[0] % 10)\n",
    "\n",
    "        for x in nums[1:]:\n",
    "            depth, pos, val = x//100, x//10 % 10, x % 10\n",
    "            pos -= 1\n",
    "            cur = root\n",
    "            for d in range(depth - 2, -1, -1):\n",
    "                if pos < 2**d:\n",
    "                    cur.left = cur = cur.left or Node(val)\n",
    "                else:\n",
    "                    cur.right = cur = cur.right or Node(val)\n",
    "\n",
    "                pos %= 2**d\n",
    "\n",
    "        def dfs(node, running_sum = 0):\n",
    "            if not node: return\n",
    "            running_sum += node.val\n",
    "            if not node.left and not node.right:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(node.left, running_sum)\n",
    "                dfs(node.right, running_sum)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.pathsum = 0\n",
    "        n = len(nums)\n",
    "        node_dict = {}\n",
    "        maxLayer = 1\n",
    "        for i in range(n):\n",
    "            layer = nums[i] // 100\n",
    "            maxLayer = max(maxLayer, layer)\n",
    "            index = (nums[i] - layer * 100) // 10\n",
    "            value = nums[i] - layer * 100 - index * 10\n",
    "            node_dict[(layer, index)] = [value, i]\n",
    "        \n",
    "        def dfs(begin, path_sum):\n",
    "            if not begin < n:\n",
    "                return\n",
    "            # path_sum = 0\n",
    "            layer = nums[begin] // 100\n",
    "            index =(nums[begin] - layer * 100) // 10\n",
    "            value = node_dict[(layer,index)][0]\n",
    "            path_sum += value\n",
    "            \n",
    "            left_index = index * 2 - 1\n",
    "            right_index = index * 2\n",
    "            if (layer+1, left_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, left_index)][1], path_sum)\n",
    "            if (layer+1, right_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, right_index)][1], path_sum)\n",
    "            if (layer+1, left_index) not in node_dict and (layer+1, right_index) not in node_dict:\n",
    "                self.pathsum += path_sum\n",
    "            \n",
    "        dfs(0, 0)\n",
    "        return self.pathsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pathSum(self, nums):\n",
    "        self.ans = 0\n",
    "        values = {x // 10: x % 10 for x in nums}\n",
    "        print(values)\n",
    "        def dfs(node, running_sum = 0):\n",
    "            if node not in values: return\n",
    "            running_sum += values[node]\n",
    "            depth, pos = divmod(node, 10)\n",
    "            left = (depth + 1) * 10 + 2 * pos - 1\n",
    "            right = left + 1\n",
    "\n",
    "            if left not in values and right not in values:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(left, running_sum)\n",
    "                dfs(right, running_sum)\n",
    "\n",
    "        dfs(nums[0] // 10)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        pos2val = {}\n",
    "        for ii in nums:\n",
    "            ii = str(ii)\n",
    "            pos = ii[:2]\n",
    "            val = ii[2]\n",
    "            pos2val[pos] = val\n",
    "\n",
    "        self.ans = 0\n",
    "        def dfs(n, current_sum):\n",
    "            n = [int(x) for x in n]\n",
    "            level, idx, val = n\n",
    "\n",
    "            current_sum += val\n",
    "            left_idx = idx * 2 - 1\n",
    "            right_idx = idx * 2\n",
    "            left_pos = f'{level + 1}{left_idx}'\n",
    "            right_pos = f'{level + 1}{right_idx}'\n",
    "            if left_pos not in pos2val and right_pos not in pos2val:\n",
    "                self.ans += current_sum\n",
    "                return\n",
    "            \n",
    "            if left_pos in pos2val:\n",
    "                dfs(left_pos + pos2val[left_pos], current_sum)\n",
    "            if right_pos in pos2val:\n",
    "                dfs(right_pos + pos2val[right_pos], current_sum)\n",
    "\n",
    "        dfs(str(nums[0]), 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        def dfs(depth, pos, cur_sum):\n",
    "            # 10x + y -> 10(x+1) + 2y-1, 10(x+1) + 2y\n",
    "            nonlocal res\n",
    "            l, r = 10 * (depth + 1) + 2 * pos - 1, 10 * (depth + 1) + 2 * pos\n",
    "            if l not in memo and r not in memo:  # leaf\n",
    "                res += cur_sum\n",
    "                return\n",
    "            if l in memo:\n",
    "                dfs(depth + 1, pos * 2 - 1, cur_sum + memo[l])\n",
    "            if r in memo:\n",
    "                dfs(depth + 1, pos * 2, cur_sum + memo[r])\n",
    "\n",
    "        memo = {}  # depth+pos: val\n",
    "        for num in nums:\n",
    "            memo[num // 10] = num % 10\n",
    "        res = 0\n",
    "        dfs(1, 1, memo[11])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        pos2val = {}\n",
    "        for ii in nums:\n",
    "            pos2val[ii // 10] = ii % 10\n",
    "        \n",
    "        self.ans = 0\n",
    "        def dfs_sum(pos, current_sum):\n",
    "            if pos not in pos2val:\n",
    "                return 0\n",
    "            \n",
    "            val = pos2val[pos]\n",
    "            current_sum += val\n",
    "            \n",
    "            level = pos // 10\n",
    "            idx = pos % 10\n",
    "            left_pos = (level + 1) * 10 + idx * 2 - 1\n",
    "            right_pos = (level + 1) * 10 + idx * 2\n",
    "            if left_pos not in pos2val and right_pos not in pos2val:\n",
    "                self.ans += current_sum\n",
    "            dfs_sum(left_pos, current_sum)\n",
    "            right = dfs_sum(right_pos, current_sum)\n",
    "        \n",
    "        dfs_sum(nums[0] // 10, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        tree = {(n // 100, n // 10 % 10): n % 10 for n in nums}\n",
    "\n",
    "        def dfs(currNode, currSum):\n",
    "\n",
    "            if not currNode in tree:\n",
    "                return 0\n",
    "\n",
    "            currSum += tree[currNode]\n",
    "            layer, pos = currNode\n",
    "            leftNode = (layer + 1, 2 * pos - 1)\n",
    "            rightNode = (layer + 1, 2 * pos)\n",
    "\n",
    "            if not leftNode in tree and not rightNode in tree:\n",
    "                return currSum\n",
    "\n",
    "            return dfs(leftNode, currSum) + dfs(rightNode, currSum)\n",
    "\n",
    "        # s = dfs((0, 0), )\n",
    "\n",
    "        return dfs((1, 1), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "\n",
    "        def recursion(pathSum, subroot):\n",
    "            if subroot.left == None and subroot.right == None:\n",
    "                if (pathSum + subroot.val) == targetSum:\n",
    "                    match.append(1)\n",
    "                    print(match)\n",
    "                    return\n",
    "            \n",
    "            pathSum += subroot.val\n",
    "            if subroot.left:\n",
    "                recursion(pathSum, subroot.left)\n",
    "            if subroot.right:\n",
    "                recursion(pathSum, subroot.right)\n",
    "            pathSum -= subroot.val\n",
    "        # debug  root = None\n",
    "        if not root: return False\n",
    "        pathSum = 0\n",
    "        match = []\n",
    "        recursion(pathSum, root)\n",
    "        if match:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        # 回溯+递归\n",
    "        # if not root:return 0\n",
    "        # def dfs(root,total):\n",
    "        #     if total+root.val==sum:\n",
    "        #         res[0] += 1\n",
    "        #     if root.left:dfs(root.left,total+root.val)\n",
    "        #     if root.right:dfs(root.right,total+root.val)\n",
    "        # res = [0]\n",
    "        # dfs(root,0)\n",
    "        # return res[0]+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)\n",
    "\n",
    "        #前缀和\n",
    "        if not root:return 0\n",
    "        value = collections.defaultdict(int)\n",
    "        value[0]=1\n",
    "        def dfs(root,total):\n",
    "            if not root:return 0\n",
    "            res = 0\n",
    "            total+=root.val\n",
    "            res+=value[total-sum]\n",
    "            value[total]+=1\n",
    "            res+=dfs(root.left,total)\n",
    "            res+=dfs(root.right,total)\n",
    "            value[total]-=1\n",
    "            return res\n",
    "        return dfs(root,0)\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.ans=0\n",
    "        pd=collections.defaultdict(int)\n",
    "        pd[0]=1\n",
    "        def dfs(node,prefix):\n",
    "            if node is None:\n",
    "                return \n",
    "            prefix+=node.val\n",
    "            self.ans+=pd[prefix-sum]\n",
    "            pd[prefix]+=1\n",
    "            # print(pd)\n",
    "            dfs(node.left,prefix)\n",
    "            dfs(node.right,prefix)\n",
    "            pd[prefix]-=1\n",
    "            prefix-=node.val\n",
    "            \n",
    "        dfs(root,0)\n",
    "        return self.ans   \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        cnt[0] = 1\n",
    "        def dfs(node, ps):\n",
    "            nonlocal ans, cnt\n",
    "            if not node:\n",
    "                return\n",
    "            ps += node.val\n",
    "            ans += cnt[ps-sum]\n",
    "            cnt[ps] += 1\n",
    "            dfs(node.left, ps)\n",
    "            dfs(node.right, ps)\n",
    "            cnt[ps] -= 1\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.ans = 0\n",
    "        if root is None:\n",
    "            return self.ans\n",
    "        self.backtrack(root, sum)\n",
    "        return self.ans + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n",
    "\n",
    "    def backtrack(self, node, target):\n",
    "        if node.val == target:\n",
    "            self.ans += 1\n",
    "        if node.left:\n",
    "            self.backtrack(node.left, target-node.val)\n",
    "        if node.right:\n",
    "            self.backtrack(node.right, target-node.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root, sum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "            if root.val == sum:\n",
    "                ret += 1\n",
    "\n",
    "            ret += rootSum(root.left, sum - root.val)\n",
    "            ret += rootSum(root.right, sum - root.val)\n",
    "            return ret\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "            \n",
    "        ret = rootSum(root, sum)\n",
    "        ret += self.pathSum(root.left, sum)\n",
    "        ret += self.pathSum(root.right, sum)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "\n",
    "        def myfun1(node1,val1):\n",
    "            if node1==None:\n",
    "                return 0\n",
    "            return myfun1(node1.left,val1-node1.val)+myfun1(node1.right,val1-node1.val)+(val1==node1.val)\n",
    "\n",
    "\n",
    "        result=0\n",
    "\n",
    "        my_list=[root]\n",
    "        while my_list:\n",
    "            temp_node=my_list.pop(0)\n",
    "            result=result+myfun1(temp_node,sum)\n",
    "            if temp_node and  temp_node.left:\n",
    "                my_list.append(temp_node.left)\n",
    "            if temp_node and temp_node.right:\n",
    "                my_list.append(temp_node.right)\n",
    "        \n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root, sum):\n",
    "            if root is None: return 0\n",
    "            ret = 0\n",
    "            if root.val == sum:\n",
    "                ret += 1\n",
    "            ret += rootSum(root.left, sum - root.val)\n",
    "            ret += rootSum(root.right, sum - root.val)\n",
    "            return ret\n",
    "        \n",
    "        if root is None: return 0\n",
    "        ret = rootSum(root, sum)\n",
    "        ret += self.pathSum(root.left, sum)\n",
    "        ret += self.pathSum(root.right, sum)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(root,sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res=0\n",
    "            if root.val==sum:\n",
    "                res+=1\n",
    "            res+=dfs(root.left,sum-root.val)\n",
    "            res+=dfs(root.right,sum-root.val)\n",
    "            return res\n",
    "        return dfs(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.rec = defaultdict(int)\n",
    "        self.rec[0] = 1\n",
    "        def dfs(node, curr):\n",
    "            if not node:\n",
    "                  return 0 \n",
    "            ret = self.rec[curr + node.val - sum]\n",
    "            self.rec[curr + node.val] += 1\n",
    "            ret += dfs(node.left, curr + node.val)\n",
    "            ret += dfs(node.right, curr + node.val)\n",
    "            self.rec[curr + node.val] -= 1\n",
    "            return ret\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root, sum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "            if root.val == sum:\n",
    "                ret += 1\n",
    "\n",
    "            ret += rootSum(root.left, sum - root.val)\n",
    "            ret += rootSum(root.right, sum - root.val)\n",
    "            return ret\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "            \n",
    "        ret = rootSum(root, sum)\n",
    "        ret += self.pathSum(root.left, sum)\n",
    "        ret += self.pathSum(root.right, sum)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import math \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        target = sum \n",
    "\n",
    "        def backtracing(path: List, res: List[List], cur_node) -> None: \n",
    "            if math.fsum(path) == target:\n",
    "                # res.append(list(path))\n",
    "                res.append(1)\n",
    "                 \n",
    "            if cur_node is None:\n",
    "                return \n",
    "\n",
    "            children = [x for x in [cur_node.left, cur_node.right] if x]\n",
    "            for child in children:\n",
    "                path.append(child.val)\n",
    "                backtracing(path, res, child)\n",
    "                path.pop()\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        def trav(root) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            backtracing([root.val], res, root)\n",
    "            trav(root.left)\n",
    "            trav(root.right)\n",
    "        \n",
    "        trav(root)\n",
    "        # print(res)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root,s):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cnt=0\n",
    "            if root.val==s:\n",
    "                cnt+=1\n",
    "\n",
    "            cnt+=rootSum(root.left,s-root.val)\n",
    "            cnt+=rootSum(root.right,s-root.val)\n",
    "            return cnt\n",
    "        if not root:\n",
    "            return 0\n",
    "        cnt=rootSum(root,sum)\n",
    "        cnt+=self.pathSum(root.left,sum)\n",
    "        cnt+=self.pathSum(root.right,sum)\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root: return 0\n",
    "\n",
    "        def dfs(node, remaining_sum):\n",
    "            if not node: return\n",
    "\n",
    "            remaining_sum -= node.val\n",
    "            if remaining_sum == 0:\n",
    "                self.ans += 1\n",
    "            \n",
    "            dfs(node.left, remaining_sum)\n",
    "            dfs(node.right, remaining_sum)\n",
    "\n",
    "        dfs(root, sum)\n",
    "        self.pathSum(root.left, sum)\n",
    "        self.pathSum(root.right, sum)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root,sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            ret=0\n",
    "            if root.val==sum:\n",
    "                ret+=1\n",
    "            ret+=rootSum(root.left,sum-root.val)\n",
    "            ret+=rootSum(root.right,sum-root.val)\n",
    "            return ret\n",
    "        if not root:\n",
    "            return 0\n",
    "        ret=rootSum(root,sum)\n",
    "        ret+=self.pathSum(root.left,sum)\n",
    "        ret+=self.pathSum(root.right,sum)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootsum(node, s):\n",
    "            if not node:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if node.val == s:\n",
    "                ans += 1\n",
    "            ans += rootsum(node.left, s - node.val)\n",
    "            ans += rootsum(node.right, s - node.val)\n",
    "            return ans\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        res = rootsum(root, sum)\n",
    "        res += self.pathSum(root.left, sum)\n",
    "        res += self.pathSum(root.right, sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def f(root, s):\n",
    "          \n",
    "            if root:\n",
    "                s += root.val \n",
    "                if s == sum:\n",
    "                    self.ans += 1 \n",
    "                if root.left:\n",
    "                    f(root.left, s)\n",
    "                  \n",
    "                if root.right:\n",
    "                    f(root.right, s)\n",
    "            return  \n",
    "\n",
    "        def g(root):\n",
    "            if root:\n",
    "                f(root, 0)\n",
    "                if root.left:\n",
    "                    g(root.left)\n",
    "                if root.right:\n",
    "                    g(root.right)\n",
    "\n",
    "        \n",
    "        g(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root,s):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cnt=0\n",
    "            if root.val==s:\n",
    "                cnt+=1\n",
    "\n",
    "            cnt+=rootSum(root.left,s-root.val)\n",
    "            cnt+=rootSum(root.right,s-root.val)\n",
    "            return cnt\n",
    "        if not root:\n",
    "            return 0\n",
    "        cnt=rootSum(root,sum)\n",
    "        cnt+=self.pathSum(root.left,sum)\n",
    "        cnt+=self.pathSum(root.right,sum)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(root,cur_sum,pre_hash):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = 0\n",
    "            cur_sum += root.val\n",
    "            self.res += pre_hash[cur_sum-sum]\n",
    "            pre_hash[cur_sum] += 1\n",
    "            res += dfs(root.left,cur_sum,pre_hash)\n",
    "            res += dfs(root.right,cur_sum,pre_hash)\n",
    "            pre_hash[cur_sum] -= 1\n",
    "            return res\n",
    "        pre_hash = collections.Counter()\n",
    "        pre_hash[0] = 1\n",
    "        dfs(root,0,pre_hash)\n",
    "        return self.res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.outnum=0\n",
    "        self.num=sum\n",
    "\n",
    "        def pathS(root,nowsum):\n",
    "            nowsum+=root.val\n",
    "            if nowsum==self.num:\n",
    "                self.outnum+=1\n",
    "\n",
    "            if root.left:\n",
    "                pathS(root.left,nowsum)\n",
    "            if root.right:\n",
    "                pathS(root.right,nowsum)\n",
    "\n",
    "        mydeque=deque()\n",
    "        if root:\n",
    "            mydeque.append(root)\n",
    "        while mydeque:\n",
    "            item=mydeque.popleft()\n",
    "            if item.left:\n",
    "                mydeque.append(item.left)\n",
    "            if item.right:\n",
    "                mydeque.append(item.right)\n",
    "\n",
    "            pathS(item,0)\n",
    "\n",
    "        return self.outnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        res = 0\n",
    "        def dfs(root, c):\n",
    "            count = 0\n",
    "            if not root:    return 0\n",
    "            if c+ root.val == sum:\n",
    "                count += 1\n",
    "\n",
    "            count+=dfs(root.left, c+root.val)\n",
    "            count+=dfs(root.right, c+root.val)\n",
    "            return count\n",
    "\n",
    "        if not root:    return 0\n",
    "        res = dfs(root, 0)\n",
    "        res += self.pathSum(root.left, sum)\n",
    "        res += self.pathSum(root.right, sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root, sum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "            if root.val == sum:\n",
    "                ret += 1\n",
    "\n",
    "            ret += rootSum(root.left, sum - root.val)\n",
    "            ret += rootSum(root.right, sum - root.val)\n",
    "            return ret\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "            \n",
    "        ret = rootSum(root, sum)\n",
    "        ret += self.pathSum(root.left, sum)\n",
    "        ret += self.pathSum(root.right, sum)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def path(root,sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if root.val == sum:\n",
    "                res += 1\n",
    "            res += path(root.left,sum-root.val)\n",
    "            res += path(root.right,sum-root.val)\n",
    "            return res\n",
    "        if not root:\n",
    "            return 0\n",
    "        return path(root,sum) + self.pathSum(root.left,sum) + self.pathSum(root.right,sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def f(root, s):\n",
    "            ans = 0\n",
    "            if root:\n",
    "                s += root.val \n",
    "                if s == sum:\n",
    "                    ans += 1 \n",
    "                if root.left:\n",
    "                    ans += f(root.left, s)\n",
    "                  \n",
    "                if root.right:\n",
    "                    ans += f(root.right, s)\n",
    "            return ans \n",
    "\n",
    "        def g(root):\n",
    "            if root:\n",
    "                self.ans += f(root, 0)\n",
    "                if root.left:\n",
    "                    g(root.left)\n",
    "                if root.right:\n",
    "                    g(root.right)\n",
    "\n",
    "        \n",
    "        g(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "\n",
    "        def rootSum(root,sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if root.val == sum:\n",
    "                res+=1\n",
    "            res+= rootSum(root.left, sum-root.val)\n",
    "            res+= rootSum(root.right, sum-root.val)\n",
    "            return res\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = rootSum(root,sum)\n",
    "        res+= self.pathSum(root.left,sum)\n",
    "        res+= self.pathSum(root.right,sum)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if(root==None):return 0\n",
    "        ans,mp=0,{0:1}\n",
    "        def dfs(rot,sumq):\n",
    "            nonlocal ans,mp\n",
    "            ans+=mp.get(sumq+rot.val-sum,0)\n",
    "            mp[sumq+rot.val]=mp.get(sumq+rot.val,0)+1\n",
    "            if(rot.left):dfs(rot.left,sumq+rot.val)\n",
    "            if(rot.right):dfs(rot.right,sumq+rot.val)\n",
    "            mp[sumq+rot.val]-=1\n",
    "        dfs(root,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        \n",
    "        def rootSum(root,s):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cnt=0\n",
    "            if root.val==s:\n",
    "                cnt+=1\n",
    "\n",
    "            cnt+=rootSum(root.left,s-root.val)\n",
    "            cnt+=rootSum(root.right,s-root.val)\n",
    "            return cnt\n",
    "        if not root:\n",
    "            return 0\n",
    "        # 先计算出包含根节点的情况\n",
    "        # 再递归求出不包含根节点的左右子树\n",
    "        return rootSum(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def dfs(self, root, sum, a, curSum):\n",
    "        if root == None:\n",
    "            return \n",
    "        curSum += root.val\n",
    "        self.res += a[curSum-sum]\n",
    "        a[curSum] += 1\n",
    "        #print(curSum)\n",
    "        self.dfs(root.left, sum, a, curSum)\n",
    "        self.dfs(root.right, sum, a, curSum)\n",
    "        a[curSum] -= 1   ###必须要从 父节点到子节点方向\n",
    "        curSum -= root.val\n",
    "        \n",
    "\n",
    "\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        a = collections.defaultdict(int)\n",
    "        a[0] = 1\n",
    "        self.dfs(root, sum, a, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    cnt=0\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        path = defaultdict(int)\n",
    "        path[0]=1\n",
    "        def dfs(node, total):\n",
    "            if not node:\n",
    "                return\n",
    "            total += node.val\n",
    "            self.cnt += path[total - sum]\n",
    "            path[total] +=1\n",
    "            dfs(node.left, total)\n",
    "            dfs(node.right, total)\n",
    "            path[total] -=1\n",
    "        dfs(root, 0)\n",
    "        return self.cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        record = collections.defaultdict(int)\n",
    "        record[0] = 1\n",
    "        def dfs(root, cur):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = 0\n",
    "            cur += root.val\n",
    "            res += record[cur-sum]\n",
    "            record[cur] += 1\n",
    "            res += dfs(root.left, cur)\n",
    "            res += dfs(root.right, cur)\n",
    "            record[cur] -= 1\n",
    "            return res\n",
    "         \n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.res = 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(node, tmp):\n",
    "            if not node:\n",
    "                return \n",
    "            tmp += node.val\n",
    "            if tmp==sum:\n",
    "                self.res += 1\n",
    "            dfs(node.left, tmp)\n",
    "            dfs(node.right, tmp)\n",
    "        dfs(root, 0)\n",
    "        self.res += self.pathSum(root.left, sum)\n",
    "        self.res += self.pathSum(root.right, sum)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        target = sum \n",
    "\n",
    "        if root is None:\n",
    "            return 0 \n",
    "\n",
    "        def dfs(root: TreeNode, path: List, res: List[int]) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            else:\n",
    "                path.append(root.val)\n",
    "\n",
    "                if math.fsum(path) == target: \n",
    "                    res[0] += 1\n",
    "                \n",
    "                for child in [root.left, root.right]:\n",
    "                    if child:\n",
    "                        dfs(child, path, res)\n",
    "                        path.pop()       \n",
    "\n",
    "            \n",
    "        res = [0]\n",
    "        \n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                cur = que.popleft()\n",
    "                dfs(cur, [], res)\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "        \n",
    "        # dfs(root, path, res)\n",
    "        # print(res)\n",
    "        return res[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def path(root,sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if root.val == sum:\n",
    "                res += 1\n",
    "            res += path(root.left,sum - root.val)\n",
    "            res += path(root.right,sum - root.val)\n",
    "            return res\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        return path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        counter = defaultdict(int)\n",
    "        counter[0] = 1\n",
    "\n",
    "        def dfs(node, cur):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            cur = cur + node.val\n",
    "            res = counter[cur-sum]\n",
    "            \n",
    "            counter[cur] += 1\n",
    "            res += dfs(node.left, cur)\n",
    "            res += dfs(node.right, cur)\n",
    "            counter[cur] -= 1\n",
    "            return res\n",
    "        \n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, target: int) -> int:\n",
    "        presum = defaultdict(int)\n",
    "        presum[0] = 1\n",
    "        ans = 0\n",
    "        def dfs(node, path):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            path += node.val\n",
    "            ans += presum[path - target]\n",
    "            \n",
    "            presum[path] += 1\n",
    "            dfs(node.left, path)\n",
    "            dfs(node.right, path)\n",
    "            presum[path] -= 1\n",
    "   \n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.rec = defaultdict(int)\n",
    "        self.rec[0] = 1\n",
    "        def dfs(node, curr):\n",
    "            if not node:\n",
    "                  return 0 \n",
    "            ret = self.rec[curr + node.val - sum]\n",
    "            self.rec[curr + node.val] += 1\n",
    "            if node.left:\n",
    "                ret += dfs(node.left, curr + node.val)\n",
    "            if node.right:\n",
    "                ret += dfs(node.right, curr + node.val)\n",
    "            self.rec[curr + node.val] -= 1\n",
    "            return ret\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "\n",
    "        def rootSum(root,sum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if root.val == sum:\n",
    "                res+=1\n",
    "            res+= rootSum(root.left, sum-root.val)\n",
    "            res+= rootSum(root.right, sum-root.val)\n",
    "            return res\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = rootSum(root,sum)\n",
    "        res+= self.pathSum(root.left,sum)\n",
    "        res+= self.pathSum(root.right,sum)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, s: int) -> int:\n",
    "        res = 0\n",
    "        p = s\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            nonlocal p\n",
    "            if not root:\n",
    "                return []\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "\n",
    "            val = [root.val]\n",
    "            if root.val == p: res += 1\n",
    "            for l in left:\n",
    "                if root.val + l == p: res += 1\n",
    "                val.append(root.val + l)\n",
    "            \n",
    "            for r in right:\n",
    "                if root.val + r == p: res += 1\n",
    "                val.append(root.val + r)\n",
    "            \n",
    "            return val\n",
    "        dfs(root)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "'''import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        target = sum \n",
    "\n",
    "        if root is None:\n",
    "            return 0 \n",
    "\n",
    "        def dfs(root: TreeNode, path: List, res: List[int]) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            else:\n",
    "                path.append(root.val)\n",
    "\n",
    "                if math.fsum(path) == target: \n",
    "                    res[0] += 1\n",
    "                \n",
    "                for child in [root.left, root.right]:\n",
    "                    if child:\n",
    "                        dfs(child, path, res)\n",
    "                        path.pop()       \n",
    "\n",
    "            \n",
    "        res = [0]\n",
    "        \n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                cur = que.popleft()\n",
    "                dfs(cur, [], res)\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "        \n",
    "        # dfs(root, path, res)\n",
    "        # print(res)\n",
    "        return res[0]\n",
    "'''\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.ans = 0\n",
    "        prefix_sum = defaultdict(int)\n",
    "        prefix_sum[0] = 1\n",
    "        def dfs(node: TreeNode, total: int):\n",
    "            if node is None:\n",
    "                return\n",
    "            total += node.val\n",
    "            self.ans += prefix_sum[total-sum]\n",
    "            prefix_sum[total] += 1\n",
    "            dfs(node.left, total)\n",
    "            dfs(node.right, total)\n",
    "            prefix_sum[total] -= 1\n",
    "        dfs(root, 0)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        # 回溯+递归\n",
    "        if not root:return 0\n",
    "        def dfs(root,total):\n",
    "            if total+root.val==sum:\n",
    "                res[0] += 1\n",
    "            if root.left:dfs(root.left,total+root.val)\n",
    "            if root.right:dfs(root.right,total+root.val)\n",
    "        res = [0]\n",
    "        dfs(root,0)\n",
    "        return res[0]+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    tmp = []\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root, sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            if root.val == sum:\n",
    "                res += 1\n",
    "            sum -= root.val\n",
    "\n",
    "            res += rootSum(root.left, sum)\n",
    "            res += rootSum(root.right, sum)\n",
    "            return res\n",
    "        if not root:\n",
    "            return 0\n",
    "        return rootSum(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        ans=0\n",
    "        def dfs(root,sum,flag):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val==sum:\n",
    "                ans+=1\n",
    "            if flag:\n",
    "                dfs(root.left, sum-root.val,1)\n",
    "                dfs(root.right, sum-root.val,1)\n",
    "            else:\n",
    "                dfs(root.left, sum,0)\n",
    "                dfs(root.right, sum,0)\n",
    "                dfs(root.left, sum-root.val,1)\n",
    "                dfs(root.right, sum-root.val,1)\n",
    "        dfs(root,sum,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root,sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if root.val == sum:\n",
    "                res += 1\n",
    "            res += rootSum(root.left,sum - root.val)\n",
    "            res += rootSum(root.right,sum - root.val)\n",
    "            return res\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = rootSum(root,sum)\n",
    "        res += self.pathSum(root.left,sum)\n",
    "        res += self.pathSum(root.right,sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def dfs(root,target):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res=0\n",
    "            target -=root.val\n",
    "            if target==0:\n",
    "                res +=1\n",
    "            res+=dfs(root.left,target)\n",
    "            res+=dfs(root.right,target)\n",
    "            return res\n",
    "        ans=0\n",
    "        if not root:\n",
    "            return 0\n",
    "        ans+=dfs(root,sum)\n",
    "        ans +=self.pathSum(root.left,sum)\n",
    "        ans+=self.pathSum(root.right,sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def dfs(root,cur_sum,pre_hash):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = 0\n",
    "            cur_sum += root.val\n",
    "            res += pre_hash[cur_sum-sum]\n",
    "            pre_hash[cur_sum] += 1\n",
    "            res += dfs(root.left,cur_sum,pre_hash)\n",
    "            res += dfs(root.right,cur_sum,pre_hash)\n",
    "            pre_hash[cur_sum] -= 1\n",
    "            return res\n",
    "        pre_hash = collections.Counter()\n",
    "        pre_hash[0] = 1\n",
    "        return dfs(root,0,pre_hash)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root, sum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "            if root.val == sum:\n",
    "                ret += 1\n",
    "\n",
    "            ret += rootSum(root.left, sum - root.val)\n",
    "            ret += rootSum(root.right, sum - root.val)\n",
    "            return ret\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "            \n",
    "        ret = rootSum(root, sum)\n",
    "        ret += self.pathSum(root.left, sum)\n",
    "        ret += self.pathSum(root.right, sum)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cnt = 0\n",
    "\n",
    "    def dfs(self, root, target):\n",
    "        if root is None:\n",
    "            return\n",
    "        target -= root.val\n",
    "        if target == 0:\n",
    "            self.cnt += 1\n",
    "        self.dfs(root.left, target)\n",
    "        self.dfs(root.right, target)\n",
    "\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        self.dfs(root, sum)\n",
    "        self.pathSum(root.left, sum)\n",
    "        self.pathSum(root.right, sum)\n",
    "        return self.cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n",
    "    \n",
    "    def path(self, root, sum):\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        if root.val == sum:\n",
    "            res += 1\n",
    "        res += self.path(root.left, sum - root.val)\n",
    "        res += self.path(root.right, sum - root.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n",
    "    \n",
    "    def path(self, root, sum):\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        if root.val == sum:\n",
    "            res += 1\n",
    "        res += self.path(root.left, sum - root.val)\n",
    "        res += self.path(root.right, sum - root.val)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root, sum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "            if root.val == sum:\n",
    "                ret += 1\n",
    "\n",
    "            ret += rootSum(root.left, sum - root.val)\n",
    "            ret += rootSum(root.right, sum - root.val)\n",
    "            return ret\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "            \n",
    "        ret = rootSum(root, sum)\n",
    "        ret += self.pathSum(root.left, sum)\n",
    "        ret += self.pathSum(root.right, sum)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def path(node: TreeNode, target):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            count = 0\n",
    "            if node.val == target:\n",
    "                count += 1\n",
    "\n",
    "            left_count = path(node.left, target - node.val)\n",
    "            right_count = path(node.right, target - node.val)\n",
    "            return count + left_count + right_count\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        return path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        # 回溯+递归\n",
    "        if not root:return 0\n",
    "        def dfs(root,total):\n",
    "            if total+root.val==sum:\n",
    "                res[0] += 1\n",
    "            if root.left:dfs(root.left,total+root.val)\n",
    "            if root.right:dfs(root.right,total+root.val)\n",
    "        res = [0]\n",
    "        dfs(root,0)\n",
    "        return res[0]+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        res = [0]\n",
    "        self.dfs(root, 0, [], sum, res)\n",
    "        return res[0]\n",
    "    def dfs(self, node, depth, path, sum, res):\n",
    "        if not node: return\n",
    "        if depth < len(path):\n",
    "            path[depth] = node.val\n",
    "        else:\n",
    "            path.append(node.val)\n",
    "        k = 0\n",
    "        for i in range(depth, -1, -1):\n",
    "            k += path[i]\n",
    "            if k == sum:\n",
    "                res[0] += 1\n",
    "        self.dfs(node.left, depth+1, path, sum, res)\n",
    "        self.dfs(node.right, depth+1, path, sum, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.ans=0\n",
    "        def getans(node):\n",
    "            def dfs(node,l,s):\n",
    "                if node is None:\n",
    "                    return \n",
    "                s+=node.val\n",
    "                l.append(node.val)\n",
    "                if s==sum:\n",
    "                    self.ans+=1\n",
    "                dfs(node.left,l,s)\n",
    "                dfs(node.right,l,s)\n",
    "                l.pop()\n",
    "                s-=node.val\n",
    "            if node is not None:\n",
    "                dfs(node,[],0)\n",
    "                getans(node.left)\n",
    "                getans(node.right)\n",
    "        getans(root)\n",
    "        return self.ans   \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:return 0\n",
    "        def dfs(root,total):\n",
    "            if total+root.val==sum:\n",
    "                res[0] += 1\n",
    "            if root.left:dfs(root.left,total+root.val)\n",
    "            if root.right:dfs(root.right,total+root.val)\n",
    "        res = [0]\n",
    "        dfs(root,0)\n",
    "        return res[0]+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        ans=0\n",
    "        def f(r,A):\n",
    "            nonlocal ans\n",
    "            if not r:\n",
    "                return\n",
    "            A.append(r.val)\n",
    "            s=0\n",
    "            for i in range(len(A)-1,-1,-1):\n",
    "                s+=A[i]\n",
    "                if s==sum:\n",
    "                    ans+=1\n",
    "            f(r.left,A)\n",
    "            f(r.right,A)\n",
    "            A.pop()\n",
    "        f(root,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root: TreeNode, sum: int) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "            if root.val == sum:\n",
    "                ret += 1\n",
    "\n",
    "            ret += rootSum(root.left, sum - root.val)\n",
    "            ret += rootSum(root.right, sum - root.val)\n",
    "            return ret\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "            \n",
    "        ret = rootSum(root, sum)\n",
    "        ret += self.pathSum(root.left, sum)\n",
    "        ret += self.pathSum(root.right, sum)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n",
    "    \n",
    "    def path(self, root, sum):\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        if root.val == sum:\n",
    "            res += 1\n",
    "        res += self.path(root.left, sum - root.val)\n",
    "        res += self.path(root.right, sum - root.val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "# https://leetcode.cn/problems/path-sum-iii/description/路径总和III原题\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        prefix=collections.defaultdict(int)\n",
    "        prefix[0]=1\n",
    "        def dfs(root,curSum):\n",
    "            # 树空\n",
    "            if not root:\n",
    "                return 0\n",
    "            # 树不空\n",
    "            cnt=0\n",
    "            curSum+=root.val\n",
    "            cnt+=prefix[curSum-sum]\n",
    "            prefix[curSum]+=1\n",
    "            cnt+=dfs(root.left,curSum)\n",
    "            cnt+=dfs(root.right,curSum)\n",
    "            prefix[curSum]-=1\n",
    "            return cnt\n",
    "        return dfs(root,0)\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n",
    "    \n",
    "    def path(self, root, sum):\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        if root.val == sum:\n",
    "            res += 1\n",
    "        res += self.path(root.left, sum - root.val)\n",
    "        res += self.path(root.right, sum - root.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        res = 0\n",
    "        def dfs(root,count, c):\n",
    "            count = 0\n",
    "            if not root:    return 0\n",
    "            if c+ root.val == sum:\n",
    "                count += 1\n",
    "\n",
    "            count+=dfs(root.left, count, c+root.val)\n",
    "            count+=dfs(root.right, count, c+root.val)\n",
    "            return count\n",
    "\n",
    "        if not root:    return 0\n",
    "        res = dfs(root,0, 0)\n",
    "        res += self.pathSum(root.left, sum)\n",
    "        res += self.pathSum(root.right, sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if root is None: \n",
    "            return 0 \n",
    "        end_in_root, end_before = self.sum_map(root) \n",
    "        return end_in_root[sum] + end_before[sum] \n",
    "\n",
    "\n",
    "    def sum_map(self, root): \n",
    "        # 返回： 以当前节点为ending，不以当前节点为ending\n",
    "        end_in_root = defaultdict(int) \n",
    "        end_before = defaultdict(int) \n",
    "        end_in_root[root.val] = 1\n",
    "\n",
    "        if root.left is not None: \n",
    "            l_map_end_in_root, l_map_end_before = self.sum_map(root.left) \n",
    "\n",
    "            for k, v in l_map_end_in_root.items(): \n",
    "                end_before[k] += v \n",
    "                end_in_root[k + root.val] += v \n",
    "\n",
    "            for k, v in l_map_end_before.items():\n",
    "                end_before[k] += v \n",
    "\n",
    "        if root.right is not None:\n",
    "            r_map_end_in_root, r_map_end_before = self.sum_map(root.right)\n",
    "\n",
    "            for k, v in r_map_end_in_root.items(): \n",
    "                end_before[k] += v \n",
    "                end_in_root[k + root.val] += v \n",
    "            \n",
    "            for k, v in r_map_end_before.items():\n",
    "                end_before[k] += v \n",
    "\n",
    "        return end_in_root, end_before"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        # 先计算出包含根节点的情况\n",
    "        def rootSum(root,s):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cnt=0\n",
    "            if root.val==s:\n",
    "                cnt+=1\n",
    "\n",
    "            cnt+=rootSum(root.left,s-root.val)\n",
    "            cnt+=rootSum(root.right,s-root.val)\n",
    "            return cnt\n",
    "        if not root:\n",
    "            return 0\n",
    "        return rootSum(root,sum)+self.pathSum(root.left,sum)+self.pathSum(root.right,sum)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        res = 0\n",
    "        def dfs(root, c):\n",
    "            if not root:    return 0\n",
    "            count = 0\n",
    "            if c+ root.val == sum:\n",
    "                count += 1\n",
    "\n",
    "            count+=dfs(root.left, c+root.val)\n",
    "            count+=dfs(root.right, c+root.val)\n",
    "            return count\n",
    "\n",
    "        if not root:    return 0\n",
    "        res = dfs(root, 0)\n",
    "        res += self.pathSum(root.left, sum)\n",
    "        res += self.pathSum(root.right, sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def rootSum(root,s):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cnt=0\n",
    "            if root.val==s:\n",
    "                cnt+=1\n",
    "\n",
    "            cnt+=rootSum(root.left,s-root.val)\n",
    "            cnt+=rootSum(root.right,s-root.val)\n",
    "            return cnt\n",
    "        if not root:\n",
    "            return 0\n",
    "        cnt=rootSum(root,sum)\n",
    "        cnt+=self.pathSum(root.left,sum)\n",
    "        cnt+=self.pathSum(root.right,sum)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, target: int) -> int:\n",
    "        presum = defaultdict(int)\n",
    "        presum[0] = 1\n",
    "        ans = 0\n",
    "        def dfs(node, path):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            path += node.val\n",
    "            if path - target in presum:\n",
    "                ans += presum[path - target]\n",
    "            presum[path] += 1\n",
    "            dfs(node.left, path)\n",
    "            dfs(node.right, path)\n",
    "            presum[path] -= 1\n",
    "   \n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        \n",
    "#         self.res = 0\n",
    "#         def dfs(node, path_sum):\n",
    "#             if not node:\n",
    "#                 return\n",
    "            \n",
    "#             new_path_sum = {}\n",
    "#             for pi_sum, count in path_sum.items():\n",
    "#                 new_pi_sum = pi_sum + node.val\n",
    "#                 if new_pi_sum == sum:\n",
    "#                     self.res += count\n",
    "#                 if new_pi_sum not in new_path_sum:\n",
    "#                     new_path_sum[new_pi_sum] = 0\n",
    "#                 new_path_sum[new_pi_sum] += count\n",
    "            \n",
    "#             if node.val not in new_path_sum:\n",
    "#                 new_path_sum[node.val] = 0\n",
    "#             new_path_sum[node.val] += 1\n",
    "            \n",
    "#             if node.val == sum:\n",
    "#                 self.res += 1\n",
    "                \n",
    "#             dfs(node.left, new_path_sum)\n",
    "#             dfs(node.right, new_path_sum)\n",
    "#             return\n",
    "        \n",
    "#         dfs(root, {})\n",
    "#         return self.res\n",
    "        prefix = collections.defaultdict(int)\n",
    "        prefix[0] = 1\n",
    "\n",
    "        def dfs(root, curr):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            ret = 0\n",
    "            curr += root.val\n",
    "            ret += prefix[curr - sum]\n",
    "            prefix[curr] += 1\n",
    "            ret += dfs(root.left, curr)\n",
    "            ret += dfs(root.right, curr)\n",
    "            prefix[curr] -= 1\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dfs(root, 0)\n",
    "        \n",
    "            \n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "#         self.res = 0\n",
    "#         def dfs(root,cur_sum,pre_hash):\n",
    "#             if not root:\n",
    "#                 return \n",
    "#             cur_sum += root.val\n",
    "#             self.res += pre_hash[cur_sum-sum]\n",
    "#             pre_hash[cur_sum] += 1\n",
    "#             dfs(root.left,cur_sum,pre_hash)\n",
    "#             dfs(root.right,cur_sum,pre_hash)\n",
    "#             pre_hash[cur_sum] -= 1\n",
    "#         pre_hash = defaultdict(int)\n",
    "#         pre_hash[0] = 1\n",
    "#         dfs(root,0,pre_hash)\n",
    "#         return self.res \n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# presum 如何解决 第一个值为0的情况\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = 0\n",
    "        self.sum = sum\n",
    "        my_dict = defaultdict(int)\n",
    "        my_dict[0] = 1\n",
    "        self.dfs(root, 0, my_dict)\n",
    "        return self.res    \n",
    "\n",
    "\n",
    "    def dfs(self, root, pre_sum, my_dict):\n",
    "        if not root:\n",
    "            return        \n",
    "        pre_sum += root.val\n",
    "        if my_dict[pre_sum - self.sum] > 0:\n",
    "            self.res += my_dict[pre_sum - self.sum]\n",
    "        my_dict[pre_sum] += 1\n",
    "        self.dfs(root.left, pre_sum, my_dict)\n",
    "        self.dfs(root.right, pre_sum, my_dict)\n",
    "        my_dict[pre_sum] -= 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def path(node: TreeNode, target):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            count = 0\n",
    "\n",
    "            if target == node.val:\n",
    "                count += 1\n",
    "\n",
    "            count += path(node.left, target - node.val) + path(node.right, target - node.val)\n",
    "\n",
    "            return count\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        return path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        target = sum \n",
    "\n",
    "        if root is None:\n",
    "            return 0 \n",
    "\n",
    "        def dfs(root: TreeNode, path: List, res: List[List]) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            else:\n",
    "                path.append(root.val)\n",
    "\n",
    "                if math.fsum(path) == target: \n",
    "                    res.append(list(path))\n",
    "                    # return \n",
    "                \n",
    "                for child in [root.left, root.right]:\n",
    "                    if child:\n",
    "                        dfs(child, path, res)\n",
    "                        path.pop()       \n",
    "\n",
    "            \n",
    "        res = []\n",
    "        \n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                cur = que.popleft()\n",
    "                dfs(cur, [], res)\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "        \n",
    "        # dfs(root, path, res)\n",
    "        # print(res)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import math \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        target = sum \n",
    "\n",
    "        def backtracing(path: List, res: List[List], cur_node) -> None: \n",
    "            if math.fsum(path) == target:\n",
    "                res.append(list(path))\n",
    "                 \n",
    "            if cur_node is None:\n",
    "                return \n",
    "\n",
    "            children = [x for x in [cur_node.left, cur_node.right] if x]\n",
    "            for child in children:\n",
    "                path.append(child.val)\n",
    "                backtracing(path, res, child)\n",
    "                path.pop()\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        def trav(root) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            backtracing([root.val], res, root)\n",
    "            trav(root.left)\n",
    "            trav(root.right)\n",
    "        \n",
    "        trav(root)\n",
    "\n",
    "        # print(res)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import math \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        target = sum \n",
    "\n",
    "        def backtracing(path: List, res: List[List], cur_node) -> None: \n",
    "            if math.fsum(path) == target:\n",
    "                res.append(list(path))\n",
    "                 \n",
    "            if cur_node is None:\n",
    "                return \n",
    "\n",
    "            children = [x for x in [cur_node.left, cur_node.right] if x]\n",
    "            for child in children:\n",
    "                path.append(child.val)\n",
    "                backtracing(path, res, child)\n",
    "                path.pop()\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        def trav(root) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            backtracing([root.val], res, root)\n",
    "            trav(root.left)\n",
    "            trav(root.right)\n",
    "        \n",
    "        trav(root)\n",
    "\n",
    "        # print(res)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        ans=[]\n",
    "        def getans(node):\n",
    "            def dfs(node,l,s):\n",
    "                if node is None:\n",
    "                    return \n",
    "                s+=node.val\n",
    "                l.append(node.val)\n",
    "                if s==sum:\n",
    "                    ans.append(deepcopy(l))\n",
    "                dfs(node.left,l,s)\n",
    "                dfs(node.right,l,s)\n",
    "                l.pop()\n",
    "                s-=node.val\n",
    "            if node is not None:\n",
    "                dfs(node,[],0)\n",
    "                getans(node.left)\n",
    "                getans(node.right)\n",
    "        getans(root)\n",
    "        return len(ans)    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return self.path_sum(root, sum, [])\n",
    "\n",
    "    def path_sum(\n",
    "        self,\n",
    "        root: Optional[TreeNode],\n",
    "        targetSum: int,\n",
    "        r_sum: List[int],\n",
    "    ) -> int:\n",
    "        sum_path = root.val + (r_sum[-1] if len(r_sum) > 0 else 0)\n",
    "        num_paths = 1 if sum_path == targetSum else 0\n",
    "        for r in r_sum:\n",
    "            if sum_path - r == targetSum:\n",
    "                num_paths += 1\n",
    "        if root.left is not None:\n",
    "            num_paths += self.path_sum(\n",
    "                root.left,\n",
    "                targetSum,\n",
    "                r_sum + [sum_path],\n",
    "            )\n",
    "        if root.right is not None:\n",
    "            num_paths += self.path_sum(\n",
    "                root.right,\n",
    "                targetSum,\n",
    "                r_sum + [sum_path],\n",
    "            )\n",
    "        return num_paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res= 0\n",
    "    def dfs(self,root,path,_sum,res):\n",
    "        if not root:\n",
    "            return \n",
    "        _sum -= root.val\n",
    "        path.append(root.val)\n",
    "        if _sum==0:\n",
    "            self.res +=1\n",
    "        self.dfs(root.left,path[:],_sum,res)\n",
    "        self.dfs(root.right,path[:],_sum,res)\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        path = []\n",
    "        self.dfs(root,path,sum,self.res)\n",
    "        self.pathSum(root.left,sum)\n",
    "        self.pathSum(root.right,sum)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res= 0\n",
    "    def dfs(self,root,path,_sum):\n",
    "        if not root:\n",
    "            return \n",
    "        _sum -= root.val\n",
    "        path.append(root.val)\n",
    "        if _sum==0:\n",
    "            self.res +=1\n",
    "        self.dfs(root.left,path[:],_sum)\n",
    "        self.dfs(root.right,path[:],_sum)\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        path = []\n",
    "        self.dfs(root,path,sum)\n",
    "        self.pathSum(root.left,sum)\n",
    "        self.pathSum(root.right,sum)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res= 0\n",
    "    def dfs(self,root,path,_sum,res):\n",
    "        if not root:\n",
    "            return \n",
    "        _sum -= root.val\n",
    "        path.append(root.val)\n",
    "        if _sum==0:\n",
    "            print(path)\n",
    "            self.res +=1\n",
    "            \n",
    "        self.dfs(root.left,path[:],_sum,res)\n",
    "        self.dfs(root.right,path[:],_sum,res)\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        path = []\n",
    "        self.dfs(root,path,sum,self.res)\n",
    "        self.pathSum(root.left,sum)\n",
    "        self.pathSum(root.right,sum)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def pathSum(self, root: TreeNode, target: int) -> int:\n",
    "        if root:\n",
    "            self.pathSumCore(root, target, [])\n",
    "            if root.left:\n",
    "                self.pathSum(root.left, target)\n",
    "            if root.right:\n",
    "                self.pathSum(root.right, target)\n",
    "        return len(self.res)\n",
    "    \n",
    "    def pathSumCore(self, root, target, temp):\n",
    "        temp = temp + [root.val]\n",
    "        target = target - root.val\n",
    "        if target == 0:\n",
    "            self.res.append(temp)\n",
    "        if (root.left):\n",
    "            self.pathSumCore(root.left, target, temp)\n",
    "        if (root.right):\n",
    "            self.pathSumCore(root.right, target, temp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def pathSum(self, root: TreeNode, target: int) -> int:\n",
    "        if root:\n",
    "            self.pathSumCore(root, target, [])\n",
    "            if root.left:\n",
    "                self.pathSum(root.left, target)\n",
    "            if root.right:\n",
    "                self.pathSum(root.right, target)\n",
    "        return len(self.res)\n",
    "    \n",
    "    def pathSumCore(self, root, target, temp):\n",
    "        temp.append(root.val)\n",
    "        if sum(temp) == target:\n",
    "            self.res.append(temp)\n",
    "        if (root.left):\n",
    "            temp1 = temp.copy()\n",
    "            self.pathSumCore(root.left, target, temp1)\n",
    "        if (root.right):\n",
    "            temp2 = temp.copy()\n",
    "            self.pathSumCore(root.right, target, temp2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSumHelper(self, root:TreeNode, s:int):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        s = [i + root.val for i in s] + [root.val]\n",
    "        return s.count(self.sum) + self.pathSumHelper(root.left, s) + self.pathSumHelper(root.right, s)\n",
    "        \n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        self.sum = sum\n",
    "        total = self.pathSumHelper(root, [])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "\n",
    "        def dfs(root, sumlist):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            \n",
    "            sumlist = [num + root.val for num in sumlist] + [root.val]\n",
    "            return sumlist.count(sum) + dfs(root.left, sumlist) + dfs(root.right, sumlist)\n",
    "        return dfs(root, [])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
